package lanqiaobei2020;

import java.math.BigInteger;
import java.util.Scanner;

public class _06八次求和 {
    /**
     * 给定正整数 n, 求 1^8 + 2^8 + · · · + n^8 mod 123456789 。其中 mod 表示取余。
     * 输入格式
     * 输入的第一行包含一个整数 n。
     * 输出格式
     * 输出一行，包含一个整数，表示答案
     */
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        BigInteger sum = BigInteger.ZERO;
        for (int i = 1; i <= n; i++) {
            BigInteger i1 = BigInteger.valueOf(i);
            BigInteger temp = i1.multiply(i1).multiply(i1).multiply(i1).multiply(i1).multiply(i1).multiply(i1).multiply(i1);
            sum = sum.add(temp);
        }
        BigInteger mod = BigInteger.valueOf(12345678);
        System.out.println(sum.mod(mod));
    }
}
